package mid.class2;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * 判断二叉树是否为完全二叉树
 */
public class Code01_TreeDP {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtils.getMirrors();
        TreeNodeUtils.printTree(treeNode);
        Info res = process(treeNode);
        System.out.println(res);
    }


    private static class Info {
        public boolean isFull; // 是否满二叉树
        public boolean isCBT; // 是否为完全二叉树
        public int high; // 高度

        public Info(boolean isFull, boolean isCBT, int high) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.high = high;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "isFull=" + isFull +
                    ", isCBT=" + isCBT +
                    ", high=" + high +
                    '}';
        }
    }

    public static Info process(TreeNode node) {
        if (node == null) {
            return new Info(true, true, 0);
        }
        // 左边 和 右边返回三个信息
        Info left = process(node.left);
        Info right = process(node.right);

        int high = Math.max(left.high, right.high) + 1; // 高度+1
        boolean isFull = left.isFull && right.isFull && left.high == right.high; // 全部满树，并且高度一样

        boolean isCBT = false;
        if (left.isFull && right.isFull && left.high == right.high) { // 左右都满，高度一样
            isCBT = true;
        } else if (left.isCBT && right.isFull && left.high == right.high + 1) {
            isCBT = true;
        } else if (left.isFull && right.isFull && left.high == right.high + 1) {
            isCBT = true;
        } else if (left.isFull && right.isCBT && left.high == right.high) {
            isCBT = true;
        }

        return new Info(isFull, isCBT, high);
    }
}
